Nguyễn Bá Thanh sinh ngày 8 tháng 4 năm 1953, quê ở xã Hòa Tiến, huyện Hòa Vang, Đà Nẵng.[19] Ông là thế hệ thứ 14 trong chi tộc Nguyễn Bá ở xã Hòa Tiến.[20] Cha ông tên là Nguyễn Bá Tùng.[20] Mẹ ông là người xinh đẹp trong vùng, lại nhanh nhẹn và tháo vát.[20] Cha mẹ ông sinh được ba người con theo thứ tự là Nguyễn Thị Hoa, Nguyễn Bá Thanh và Nguyễn Bá Bình.[20] Chị gái Nguyễn Thị Hoa hơn ông bốn tuổi.[20] Em trai ông là Nguyễn Bá Bình sau này kết hôn với bà Thái T. T. Thủy sinh ra Nguyễn Bá Trung, Nguyễn Thị N. Hiếu và Nguyễn Bá Hậu.[20][21][22][23]

Năm 1954, sau Hiệp định Geneve, cha ông tập kết ra Bắc, mẹ, chị và ông ở lại Đà Nẵng.[23] Cha ông, ông Nguyễn Bá Tùng, sau này hi sinh, được phong liệt sĩ, Anh hùng Lực lượng Vũ trang Nhân dân.[24] Sau đó chị ông mất lúc 10 tuổi vì bệnh cảm sốt do nhà ông nghèo không có tiền cứu chữa.[23]